#pragma once
#include <iostream>
#include <vector>

template<class T>
void swap(T& a, T& b)
{
    T tmp = a;
    a = b;
    b = tmp;
}

// 冒泡排序
template<class T>
void bubble_sort(std::vector<T>& arr)
{
    int n = arr.size();
    if(n <= 1) return;

    for(int i = 0; i < n - 1; i++)
    {
        bool flag = false;
        for(int j = 0; j < n - i - 1; j++)
        {
            if(arr[j] > arr[j + 1])
            {
                swap<T>(arr[j], arr[j + 1]);
                flag = true;
            }
        }
        if(!flag) break;
    }
}

// 插入排序
template<class T>
void insert_sort(std::vector<T>& arr)
{
    int n = arr.size();
    if(n <= 1) return;

    for(int i = 1; i < n; i++)
    {
        for(int j = i; j > 0; j--)
        {
            if(arr[j] < arr[j - 1])
            {
                swap(arr[j], arr[j - 1]);
            }
            else break;
        }
    }
}

// 选择排序
template<class T>
void select_sort(std::vector<T>& arr)
{
    int n = arr.size();
    if(n <= 1) return;

    int left = 0, right = n - 1;
    while(left < right)
    {
        int min_index = left, max_index = right;
        for(int i = left; i <= right; i++)
        {
            if(arr[i] < arr[min_index]) min_index = i;
            if(arr[i] > arr[max_index]) max_index = i;
        }
        swap(arr[min_index], arr[left]);
        if(!(max_index == left && min_index == right))
            swap(arr[max_index], arr[right]);
        left++;
        right--;
    }
}

// 快速排序
template<class T>
void quick_sort(std::vector<T>& arr, int begin = 0, int end = 0)
{
    if(begin >= end) return;
    int pos = begin + (end - begin) / 2;
    int left = begin, right = end;
    while(left < right)
    {
        while(left < right && arr[right] > arr[pos]) right--;
        swap(arr[pos], arr[right]);
        pos = right;
        while(left < right && arr[left] < arr[pos]) left++;
        swap(arr[pos], arr[left]);
        pos = left;
    }
    quick_sort(arr, begin, left - 1);
    quick_sort(arr, left + 1, end);
}

// 归并排序
template<class T>
void merge_sort(std::vector<T>& arr, int begin = 0, int end = 0)
{
    if(begin >= end) return;
    static std::vector<T> tmp(end - begin + 1);

    int mid = begin + (end - begin) / 2;
    merge_sort(arr, begin, mid);
    merge_sort(arr, mid + 1, end);
    
    int i = begin;
    int left = begin, right = mid + 1;
    while(left <= mid && right <= end)
    {
        if(arr[left] <= arr[right])
            tmp[i++] = arr[left++];
        else
            tmp[i++] = arr[right++];
    }
    while(left <= mid) tmp[i++] = arr[left++];
    while(right <= end) tmp[i++] = arr[right++];
    for(int k = begin; k <= end; k++)
        arr[k] = tmp[k];
}

// 堆排序
template<class T>
class Heap
{
public:
    Heap(std::vector<int>& arr)
    :_v(arr)
    {
        adjust_up();
    }

    T top()
    {
        return _v.front();
    }

    void pop()
    {
        int n = _v.size();
        swap(_v[0], _v[n - 1]);
        _v.pop_back();
        adjust_down(0);
    }

    bool empty()
    {
        return _v.size() == 0;
    }

private:
    void adjust_up()
    {
        // 建堆 自底向上进行向下调整
        int n = _v.size();
        int parent = n - 1;
        while(parent >= 0)
        {
            adjust_down(parent);
            parent--;
        }
    }

    void adjust_down(int parent)
    {
        int n = _v.size();
        int child_l = 2 * parent + 1;
        while(child_l < n)
        {
            int child_r = child_l + 1;
            int min_child = child_l;
            if(child_r < n) min_child = _v[child_l] < _v[child_r] ? child_l : child_r;

            if(_v[min_child] < _v[parent])
            {
                swap(_v[min_child], _v[parent]);
                parent = min_child;
                child_l = 2 * parent + 1;
            }
            else break;
        }
    }

private:
    std::vector<T>& _v;
};

// 希尔排序
template<class T>
void shell_sort(std::vector<T>& arr)
{
    int n = arr.size();
    if(n <= 1) return;
    int gap = n;
    while(gap > 1)
    {
        gap /= 2;
        for(int i = gap; i < n; i++)
        {
            for(int j = i; j >= gap; j -= gap)
            {
                if(arr[j] < arr[j - gap])
                {
                    swap(arr[j], arr[j - gap]);
                }
                else break;
            }
        }
    }
}
